package listnode

import (
	"fmt"
	"gitee.com/ChanYeung/go-utils/collections"
)

// ListNode Definition for singly-linked list.
type ListNode struct {
	Val  int
	Next *ListNode
}

func (node *ListNode) DebugInfo() {
	//因为只是遍历 node中的内容，不能改变node的指向信息，所以copy一份
	copyHead := &ListNode{Val: node.Val, Next: node.Next}

	for copyHead != nil {
		fmt.Printf("%v\t", copyHead.Val)
		copyHead = copyHead.Next
	}
	fmt.Println()
}

func CreateListNode(list []int) *ListNode {
	header := &ListNode{}
	mask := header
	for _, v := range list {
		mask.Next = &ListNode{Val: v}
		mask = mask.Next
	}
	return header.Next
}

// DeleteNode /*请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。
//删除链表中的某节点
func DeleteNode(node *ListNode) {
	//思路：因为没法找到指定的HEAD节点，无法取到前序节点，所以可以改头换面，使用下一个节点的值作为指定节点的值，然后删除下一个节点
	node.Val = node.Next.Val
	node.Next = node.Next.Next
}

// RemoveNthFromEnd 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]
func RemoveNthFromEnd(head *ListNode, n int) *ListNode {
	fast := head
	slow := head
	//fast移n步，
	for i := 0; i < n; i++ {
		fast = fast.Next
	}
	//如果fast为空，表示删除的是头结点
	if fast == nil {
		return head.Next
	}

	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}
	//这里最终slow不是倒数第n个节点，他是倒数第n+1个节点，
	//他的下一个结点是倒数第n个节点,所以删除的是他的下一个结点
	slow.Next = slow.Next.Next
	return head

}

// RemoveNthFromEndWithRecursion RemoveNthFromEnd 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]
func RemoveNthFromEndWithRecursion(head *ListNode, n int) (*ListNode, int) {
	if head == nil {
		//找到尾巴节点
		return nil, 0
	}
	node, height := RemoveNthFromEndWithRecursion(head.Next, n)
	if height == n {
		//找到倒数n-1个数
		head.Next = head.Next.Next
	}
	return node, height + 1
}

// ReverseList 反转链表
//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
func ReverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	reverse := ReverseList(head.Next) //5
	head.Next.Next = head
	head.Next = nil
	return reverse //返回的头节点固定
}

//合并两个有序链表
//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
func MergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}
	head := new(ListNode)
	copyNewList := head
	for list1 != nil && list2 != nil {
		if list1.Val <= list2.Val {
			copyNewList.Next = list1
			copyNewList = copyNewList.Next
			list1 = list1.Next
		} else {
			copyNewList.Next = list2
			copyNewList = copyNewList.Next
			list2 = list2.Next
		}
	}
	if list1 != nil {
		copyNewList.Next = list1
	}
	if list2 != nil {
		copyNewList.Next = list2
	}
	return head.Next ////头节点不使用
}

// IsPalindromeWithStack 回文链表
//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
func IsPalindromeWithStack(head *ListNode) bool {
	stack := collections.NewStack()
	for head != nil {
		if stack.Peak() == head.Val {
			stack.Pop()
		} else {
			stack.Push(head.Val)
		}
		head = head.Next
	}
	if stack.Len() == 0 {
		return true
	}
	return false
}

// IsPalindrome IsPalindromeWithStack 回文链表
//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
func IsPalindrome(head *ListNode) bool {
	var nodeList []int
	for head != nil {
		nodeList = append(nodeList, head.Val)
		head = head.Next
	}
	start := 0
	end := len(nodeList) - 1
	for start < end {
		if nodeList[start] != nodeList[end] {
			return false
		}
		start++
		end--
	}
	return true
}

/*给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。
*/
func hasCycle(head *ListNode) bool {
	fast := head
	slow := head
	for fast != nil || fast.Next != nil {
		if fast == slow { //如果相遇说明有环
			return true
		}
		fast = fast.Next.Next //快针 2倍速度
		slow = slow.Next
	}
	return false
}

func MergeNodeListWithRecursion(list []*ListNode) *ListNode {
	var mergeInternal func(l, r *ListNode) *ListNode
	mergeInternal = func(l, r *ListNode) *ListNode {
		if l == nil {
			return r
		}
		if r == nil {
			return l
		}
		if l.Val < r.Val {
			l.Next = mergeInternal(l.Next, r)
			return l
		} else {
			r.Next = mergeInternal(l, r.Next)
			return r
		}
	}
	var result *ListNode
	result = list[0]
	if len(list) > 1 {
		for i := 1; i < len(list); i++ {
			result = mergeInternal(result, list[i])
		}
	}
	return result
}

/**
合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

*/
func mergeKLists(lists []*ListNode) *ListNode {
	var result *ListNode
	var interMergeNodeList func(na, nb *ListNode) *ListNode
	interMergeNodeList = func(na, nb *ListNode) *ListNode {
		if na == nil {
			return nb
		}
		if nb == nil {
			return na
		}
		//合并
		head := &ListNode{}
		mask := head
		for na != nil && nb != nil {
			if na.Val > nb.Val {
				mask.Next = nb
				nb = nb.Next
			} else {
				mask.Next = na
				na = na.Next
			}
			mask = mask.Next
		}
		if na != nil {
			mask.Next = na
		}
		if nb != nil {
			mask.Next = nb
		}
		return head.Next
	}

	for i := 0; i < len(lists); i++ {
		result = interMergeNodeList(result, lists[i])
	}
	return result
}
